package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-04
 */

import java.util.Arrays;

/**
 * 给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
 */
public class leetcode611 {
    public int triangleNumber(int[] nums) {
        if (nums.length<3) return 0;
        Arrays.sort(nums);
        int len = nums.length;
        int ans = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                int L = j+1, R = len-1, k=j;
                while (L<=R){
                    int mid = (L+R)>>1;
                    if (nums[i]+nums[j]<=nums[mid]) R = mid-1;
                    else {
                        L = mid+1;
                        k = mid;
                    }
                }
                ans += k-j;
            }
        }
        return ans;
    }
}
